Search results for "Hopcroft’s minimization algorithm"

showing 3 items of 3 documents

On extremal cases of Hopcroft’s algorithm

2010

AbstractIn this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata as…

Discrete mathematicsFinite-state machineGeneral Computer ScienceUnary operationWord treesStandard treesAutomatonTheoretical Computer ScienceCombinatoricsDeterministic finite automatonDFA minimizationDeterministic automatonHopcroft’s minimization algorithmTree automatonDeterministic finite state automataTime complexityAlgorithmComputer Science::Formal Languages and Automata TheoryMathematicsComputer Science(all)Theoretical Computer Science
researchProduct

Circular sturmian words and Hopcroft’s algorithm

2009

AbstractIn order to analyze some extremal cases of Hopcroft’s algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton Ax associated to (x). The combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. We prove that the shape of this tree uniquely characterizes the word itself. The properties of the run of Hopcroft’s algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of Hopcroft’s alg…

Discrete mathematicsReduction (recursion theory)Fibonacci numberGeneral Computer ScienceHopcroft'algorithmSturmian wordSturmian wordSturmian morphismsTheoretical Computer ScienceCombinatoricsTree (descriptive set theory)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputer Science::Discrete MathematicsDeterministic automatonHopcroft’s minimization algorithmCircular sturmian wordsTree automatonDeterministic finite state automataTime complexityAlgorithmComputer Science::Formal Languages and Automata TheoryWord (group theory)Computer Science(all)MathematicsTheoretical Computer Science
researchProduct

On Extremal Cases of the Hopcroft's Algorithm

2010

In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated…

Hopcroft’s minimization algorithmStandard treeDeterministic finite state automataWord trees
researchProduct